package com.binaryTree;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.stream.Collectors;

public class FindModeinBinarySearchTree0306_501 {

    //中序遍历-不使用额外空间，利用二叉搜索树特性
    ArrayList<Integer> resList;
    int maxCount;
    int count;
    TreeNode pre;
    public int[] findMode1(TreeNode root) {
        resList = new ArrayList<>();
        maxCount = 0;
        count = 0;
        pre = null;
        findModeCount(root);
        int[] res = new int[resList.size()];
        for (int i = 0; i < resList.size(); i++) {
            res[i] = resList.get(i);
        }
        return res;
    }

    private void findModeCount(TreeNode root) {
        if(root == null) return;
        findModeCount(root.left);

        int rootVal = root.val;
        if(pre == null || rootVal != pre.val) count = 1;
        else count++;
        if(count > maxCount){
            resList.clear();
            resList.add(rootVal);
            maxCount = count;
        } else if (count == maxCount) {
            resList.add(rootVal);
        }
        pre = root;

        findModeCount(root.right);
    }



    //暴力
    public int[] findMode(TreeNode root) {
        Map<Integer,Integer> map = new HashMap<>();
        List<Integer> list = new ArrayList<>();
        if(root == null) return null; //return list.stream().mapToInt(Integer::inValue).toArray();

        //获得频率 Map
        searchBST(root, map);
        List<Map.Entry<Integer, Integer>> mapList = map.entrySet().stream().sorted((o1, o2) -> o2.getValue().compareTo(o1.getValue())).collect(Collectors.toList());
        list.add(mapList.get(0).getKey());
        for (int i = 1; i < mapList.size(); i++) {
            if(mapList.get(i).getValue() == mapList.get(i-1).getValue()){
                list.add(mapList.get(i).getKey());
            }else break;
        }
        return list.stream().mapToInt(Integer::intValue).toArray();
    }

    private void searchBST(TreeNode root, Map<Integer, Integer> map) {
        if(root == null) return;
        map.put(root.val, map.getOrDefault(root.val,0)+1);
        searchBST(root.left,map);
        searchBST(root.right,map);
    }
}
